package LeetCode;

/**
 * @Classname LC416
 * @Description // https://leetcode-cn.com/problems/partition-equal-subset-sum/ 动态规划 子集划分
 * @Date 2021/4/20 21:23
 * @Created by yin
 */
public class LC416 {
    public boolean canPartition(int[] nums) {
        int he = 0;
        for (int i : nums) he += i;
        if (he % 2 == 1) return false;
        int target = he / 2;
        // dp[i][j]表示对于前i个物品，当前背包的容量为j时，是否能够恰好放满整个背包
        boolean[][] dp = new boolean[nums.length + 1][target + 1];
        for (int i = 0; i <= nums.length; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                if (j - nums[i - 1] < 0) dp[i][j] = dp[i - 1][j]; // 如果背包容量不足，不能装入
                else dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i - 1]]; // 装入或者不装入背包
            }
        }
        return dp[nums.length][target];
    }

    public boolean canPartition2(int[] nums) {
        int he = 0;
        for (int i : nums) he += i;
        if (he % 2 == 1) return false;
        int target = he / 2;
        // dp[j] 表示对于前i个物品，当前背包的容量为j时，是否能够恰好放满整个背包 。
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int j = target; j >= 0; j--) { // 01 背包需要反向遍历
                if (j - num >= 0) dp[j] = dp[j] | dp[j - num]; // 如果背包容量不足，不能装入
            }
        }
        return dp[target];
    }
}
